When a data sequence is read from a magnetic hard disk using a hard disk drive, the data sequence can be estimated by running the signal samples at the output of the channel through a trellis sequence detector. The trellis sequence detector computes a most likely input sequence associated with the signal samples. The most likely input sequence is the sequence through a trellis that is closest to the signal samples in Euclidean space.
A trellis diagram represents a time sequence of sample values and the possible recorded input sequences that could have produced the sample sequence. A Viterbi detector is a trellis sequence detector that finds the most likely trellis path among all possible trellis paths in a trellis diagram based on a metric value associated with each trellis path.
When a long parity code is used, it becomes very complex to implement a Viterbi detector so as to enforce the parity code constraints along the trellis, because the number of trellis states of the Viterbi detector increases exponentially with the number of parity bits in the parity code.
A parity post processor (PPP) is a signal processing module added to a conventional Viterbi detector to enforce a parity code constraint and/or to re-compute more accurate trellis path metric values based on a longer target polynomial than the one used by the Viterbi detector. Among all the trellis paths that the PPP evaluates, the PPP picks the trellis path that also satisfies the parity constraint and makes corrections to the Viterbi output accordingly.
FIG. 1 illustrates an example of a decoding system that includes a parity post processor (PPP). The decoding system receives a stream of equalized samples. The equalized samples are generated from an equalizer (not shown) based on a read sequence from a magnetic disk. A Viterbi detector 102 outputs the most likely trellis path.
Synthetic waveform block 106 remodulates the output of Viterbi detector 102 into an estimated sequence of ideal sample values. An adder 108 subtracts these ideal sample values from a delayed version of the equalized samples to generate a sequence of sample error values. The sample error values represent the noise in the read sequence. Delay block 104 accounts for the delay of detector 102 to ensure that corresponding blocks of data are received at both inputs of adder 108 at the same time.
Two paths through the trellis that differ in a single bit, differ in multiple sample values. Filter 110 filters the sample error values to compute the difference in the metric values between the detected path through the trellis and a path that differs by a single bit.
The output of Viterbi detector 102 is passed through a delay block 114 to error event pattern matching block 120 as the preliminary detected binary sequence. Block 120 attempts to match a predefined set of error events to the preliminary detected binary sequence. The predefined error events represent the most likely error events. They are a subset of all of the possible error events.
Block 120 analyzes each set of bits in a sliding window. The sliding window moves across each codeword, as shown in FIG. 1. In this example, there are 10 bits in each codeword. The illustrative error event shown in block 120 is an alternating error affecting five data bits. This error is denoted +-+-+ and corresponds to a recorded binary sequence . . . WXYZ01010ABCD . . . being incorrectly detected as . . . WXYZ10101ABCD . . . where ABCDWXYZ can each take values of one or zero and are detected correctly.
This error event can only occur if the detected data contains a string of five alternating bit values 10101 or 01010. Therefore, a sliding window of five bits is examined, and the error event is declared valid with positive sign if the detected data in the window is 10101 and valid with negative sign if it is 01010. When an error event occurs near the edge of a codeword, bits in an adjacent codeword must be examined in order to qualify the error event.
Error event pattern matching block 120 generates a valid signal that indicates which of the predefined error events matches the bits in each sliding window. If block 120 indicates that a particular error event is valid for the bits within a sliding window, block 112 causes an error pattern correlator to correlate the sample error values from block 110 with that valid error event. Block 112 generates error metric values that indicate the likelihood that each valid error event is the correct one. An error metric indicates a probability that a set of the sample error values is caused by a particular error event.
Error event pattern matching block 120 also determines the sign of the error event. The error event sign is multiplied by the output of the error pattern correlator to correct the sign of the error event in block 112.
Error event pattern matching block 120 also generates a threshold value. The threshold value is an offset value that is derived from evaluating the trellis path of an error event. The threshold value varies in response to the bits that are next to the error bits. The threshold value is subtracted from the sign-corrected output of the error correlator to generate an error metric in block 112. Block 112 generates an error metric value for each valid error event that matches bits within any of the sliding windows.
Error event pattern matching block 120 also computes the syndrome value for each valid error event using a parity check equation. There are 2 possible syndrome values, 1 and 0.
Most likely error event generator block 130 selects the error event that has the smallest error metric value and a syndrome value of 1 as the most likely error event. A preliminary detected binary sequence that has a syndrome of 1 (i.e., odd parity) is indicative of an error in the codeword.
Error correction is then applied to the preliminary detected binary sequence to correct the error based on the most likely error event selected in block 130, which includes the error location and the error event type. The PPP of FIG. 1 does not consider error events that generate syndromes with even parity (i.e., a syndrome value of 0), even though many error events do not change the parity value of blocks.
Hard-decision decoding takes binary bits as input, assumes all bits are equally likely to be in error, and decodes by flipping as few bits as possible to produce a valid codeword. Hard decoding uses special algebraic properties of the code to decode efficiently, even for very powerful codes.
One type of two-stage decoder uses a hard-decoded tensor product code, where the second component code of the tensor product code is a hard-decoded BCH code. Reed Solomon ECC decoding is another example of hard-decision decoding. Because hard decision decoding assumes all bits are equally likely to be in error, it does not consider that some bits are more reliable than others.
Error correction can also be performed by soft-decision decoding. Soft-decision decoding receives input analog data (e.g., an equalized read-back signal or bit reliability information) and preferentially flips unreliable bits. Soft-decision decoding out-performs hard-decision decoding, because it is able to exploit the fact that some bits are more reliable than others.
However, it can be difficult to decode powerful codes efficiently using soft decoding. Also, existing soft-decoded parity codes span multiple Reed-Solomon (RS) symbols. Therefore, it would be desirable to provide error correction decoding techniques with greater performance and reliability.